package sort.leetcode.medium;

import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;

/**
 * @author bruin_du
 * @description 数组中的第 k 大的数字
 * @date 2022/8/31 0:07
 **/
public class OfferII076_FindKthLargest {
    ThreadLocalRandom random = ThreadLocalRandom.current();
    public int findKthLargest(int[] nums, int k) {
        int x = -1,left = 0, right = nums.length - 1,index = 0;
        while (left < right && x != k) {
            index = partition(nums, left, right);
            x = nums.length - index;
            if (x > k) {
                left = index + 1;
            } else if (x < k) {
                right = index - 1;
            } else {
                return nums[index];
            }
        }
        return nums[left];
    }

    private int partition(int[] nums, int left, int right) {
        int index = random.nextInt(left, right);
        swap(nums, left, index);
        int v = nums[left], l = left, r = left + 1;
        while (r <= right) {
            if (nums[r] < v) {
                swap(nums, ++l, r);
            }
            r++;
        }
        swap(nums, left, l);
        return l;
    }

    private void swap(int[] nums, int x1, int x2) {
        int tmp = nums[x1];
        nums[x1] = nums[x2];
        nums[x2] = tmp;
    }

    public static void main(String[] args) {
        OfferII076_FindKthLargest offer = new OfferII076_FindKthLargest();
        System.out.println(offer.findKthLargest(new int[]{3, 2, 1, 5, 6, 4}, 2));
    }
}
